1. Field of the Invention
This invention relates to the multicast transmission and more particularly relates to methods and systems for optimal group key management for secure multicast communication. An Optimal Group Keying (OGK) scheme is disclosed that achieves both the non-colluding and storage-communication optimality. In the disclosed OGK, a group controller (GC) is responsible for key generation and distribution to group members (GM) and the group data are encrypted by a group key (GK).
2. Description of the Related Art
IP multicast is used to distribute data to a group of receivers efficiently. The efficiency can be achieved because a datagram is transmitted once at the source and any packet forwarding link in the network, saving the cost of the sender as well as network bandwidth.
Multicast group key distribution schemes have been proposed to secure one-to-many group data distribution using IP multicast. Existing solutions restrict the group memberships by encrypting the data using a symmetric Group Key (GK). One of critical requirements of secure group communication is to ensure only legitimated group members to have the update-to-date GKs when group members join or leave the group dynamically. This requirement is usually achieved through a group rekeying procedure, in which a centralized group controller updates the GKs for all legitimate group members.
Group membership revocation is usually a more difficult situation than group membership addition due to the fact that the number of formations of revoked group members is potentially large, and thus the group controller needs to preinstall auxiliary secrets for each group member just for revocation purposes. For example, in a case where an arbitrary set of members L are revoked from a group G is considered, a rekeying message should be generated and distributed to each of G \L remaining members, who use their preinstalled auxiliary secrets to decipher the rekeying message. Thus, the problem of revoking any arbitrary set of members L can be transformed to solving an exponentially increasing key distribution problem.
To address the scalability issue of the membership revocation in secure group communication, rooted-tree based key distribution schemes have been proposed. In these schemes (illustrated in FIGS. 1 and 2), each member is distributed log2 N secrets for group management (i.e., revocation and addition). It is proved that assigning log2 N secrets to each member is the information theoretical optimal storage strategy when group size is N.
The rooted-tree structure (see FIG. 1 and FIG. 2) is constructed such that each group member is assigned a unique leaf node in the tree. Every node in the tree, including leaf and non-leaf nodes, is assigned a unique auxiliary secret. Each group member is pre-distributed a set of auxiliary symmetric secrets (or keys) that are along the path from the leaf to the root, in which the root secret is GK for the entire group. Using rooted-tree based solutions, an auxiliary secret can be shared among a partition of members, and a member can be involved in multiple partitions. Typically, the a-ary rooted-tree based solutions require O(loga N) storage overhead for each member, where N is the group size. The rooted-tree based multicast group key distribution scheme can be divided into two categories: Non-Flat-Table schemes (FIG. 1) and Flat-Table schemes (FIG. 2).
Non-Flat-Table includes rooted-tree based schemes, such as One-Way Function Trees (OFT), Logical Key Hierarchy Protocol (LKH), and Efficient Large-Group Key Distribution (ELK). One important feature of these schemes is there are ad distinct secrets at level d in the key distribution tree as illustrated in FIG. 1. In other words, each node is associated with a unique secret. The secrets are not necessarily just pre-distributed random symmetric keys. They may be generated using one-way hash function or pseudo random number generator. Non-Flat-Table schemes only improve the efficiency marginally. This is because, in these solutions, based on the loga N pre-distributed auxiliary keys, each group member can merely decrypt loga N encrypted streams, as illustrated in FIG. 1.
Flat-Table schemes adopt a slightly different construction, as illustrated in FIG. 2. In Flat-Table schemes, each group member is issued a unique binary ID b0b1 . . . bn−2bn−1 of length n. In addition to the GK, group controller generates 2n auxiliary key encryption keys (KEK) {Ki,b|iεZn, bε{0,1}}. A group member with ID b0b1 . . . bn−2bn−1 holds KEKs {Ki,bi|iεZn}. The KEKs are organized in the key distribution tree in FIG. 2, where each level corresponding to one bit position in a user's ID. Thus, at each level in the Flat-Table key distribution tree, there are exact 2 distinct KEKs, which map to a bit position in ID. For example, in the FIG. 2, member with ID 011 is predistributed {K11, K22, K32}. In Flat-Table, the number of partitions each group member can participate is maximized to 2log2N−1=N−1.
Despite its efficiency, Flat-Table schemes are vulnerable to collusion attacks since FT solutions simply adopt the symmetric KEKs. For example, GMs 001 and 010 can decrypt ciphertexts destined to other GMs, e.g., 011, 000, by combining their symmetric KEKs. To prevent the collusion attacks, CP-ABE-FT was proposed to implement the FT using CP-ABE. However, message size of CP-ABE-FT is linearly growing and, thus, the communication overhead is actually log22N. Also, CP-ABE-FT utilizes a periodic refreshment mechanism to ensure forward secrecy. If the ID of a revoked GM is re-assigned to another GM before the refreshment, the revoked GM can regain the access to group data and then the group forward secrecy is compromised.
Broadcast Encryption (BE) was also introduced, where a broadcaster encrypts a message for some set of users who are listening to a broadcasting channel and use their private keys to decrypt the message. Compared with traditional one-to-one encryption schemes, BE features superior efficiency. Instead of sending messages encrypted with each individual recipient's public key, the broadcast encrypter broadcasts one encrypted message to be decrypted by multiple recipients with their own private keys.
Although existing BE schemes feature small or constant ciphertext, the number of public key or private key each user needs to perform encryption or decryption are linear on the max number of non-colluding users in the system. In the case where the BE scheme is fully collusion-resistant, the number of public/private key each user needs to store equals to the number of users in the system. For example, in the existing BE system with N users, each user uiε{1, . . . , N} is generated a public key PKi and a private key SKi. To encrypt a message to a set of users S, the encrypting method takes input of the set of public keys for all recipients {PKi|∀uiεS} and output the ciphertext. To decrypt a message, the decrypting method takes input of the private key SKi of user ui and the set of all public keys {PKi|∀uiεS} to recover original message. OGK supports many-to-many subgroup communication with O(log2 N) storage overhead on GMs.